/*
剑指 Offer II 015. 字符串中的所有变位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 变位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

变位词 指字母相同，但排列不同的字符串。

 

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的变位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的变位词。
 示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的变位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的变位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的变位词。
 

提示:

1 <= s.length, p.length <= 3 * 104
s 和 p 仅包含小写字母
 

注意：本题与主站 438 题相同： https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/
*/

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int n = s.length();
        int m = p.length();
        
        if (m > n)
        {
            return {};
        }

        vector<int> cnt(26);

        for(int i = 0; i < m; ++i)
        {
            --cnt[p[i] - 'a'];
            ++cnt[s[i] - 'a'];
        }

        vector<int> resultIndex;
        int diff = 0;
        for (int num:cnt )
        {
            if(num != 0)
            {
                ++diff;
            }
        }

        if(diff == 0)
        {
            resultIndex.push_back(0);
        }

        //slide window
        //startIndex to be leave index(left side)
        //curIndex denote right side
        //keep length = m (p's length)
        for(int j = m; j < n; ++j)
        {
            int startIndex = s[j - m] - 'a';
            int curIndex = s[j] - 'a';

            if(cnt[startIndex] == 0)
            {
                ++diff;
            }

            --cnt[startIndex];
            if(cnt[startIndex] == 0)
            {
                --diff;
            }

            if(cnt[curIndex] == 0)
            {
                ++diff;
            }

            ++cnt[curIndex];
            if(cnt[curIndex] == 0)
            {
                --diff;
            }

            if(diff == 0)
            {
                resultIndex.push_back(j - m + 1);
            }
        }

        return resultIndex;
    }

    vector<int> findAnagrams2(string s, string p)
    {
        int n = s.length();
        int m = p.length();
        
        if (m > n)
        {
            return {};
        }

        vector<int> resultIndex;
        vector<int> cnt(26);
        for (int i = 0; i < m; ++i)
        {
            --cnt[p[i] - 'a'];
        }

        //slide window
        //slide the window length until length = p's length
        int left = 0;
        for(int right = 0; right < n; ++right)
        {
            ++cnt[s[right] - 'a'];
            //right character not show in p
            while(cnt[s[right] - 'a'] > 0)
            {
                //slide left towards right
                //after while left = right + 1
                --cnt[s[left] - 'a'];
                ++left;
            }

            int slidewindowLength = right - left + 1;
            if(slidewindowLength == m)
            {
                resultIndex.push_back(left);
            }
        }

        return resultIndex;
    }
};